package num22;

import java.util.ArrayList;
import java.util.List;

/**
 * @author : DuJiabao
 * @Date : 2021/2/6 22:54
 * @Project : sword-finger-offer
 * @File : null.java
 * @Desc :数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * 解法：只要保证，加入的左括号，一定比右括号多，才能加右括号，那就可以解决了。
 */
public class Solution {
  public static void main(String[] args) {
    Solution solution = new Solution();
    List<String> strings = solution.generateParenthesis(3);
    System.out.println(strings);
  }

  public List<String> generateParenthesis(int n) {
    List<String> list = new ArrayList<>();
    method(list, "", n, n);
    return list;
  }

  private void method(List<String> list, String str, int left, int right) {
    if (left == 0 && right == 0)
      list.add(str);
    if (left > 0)
      method(list, str + "(", left - 1, right);
    if (right > left)  // left最少也是0嘛，所以可以保证right也为0
      method(list, str + ")", left, right - 1);
  }
}
